import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
private char val;
private TreeNode left;
private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode create(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
     A.left=B;
     A.right=C;
     B.left=D;
     B.right=E;
     E.right=H;
     C.left=F;
     C.right=G;
        return A;

    }
    public void prevOrder(TreeNode root){//前序遍历，递归
        if (root==null)
            return;
        System.out.print(root.val+" ");
        prevOrder(root.left);
        prevOrder(root.right);
    }
public void inOrder(TreeNode root){//中序遍历
    if (root==null)
        return;
    inOrder(root.left);
    System.out.print(root.val+" ");
    inOrder(root.right);
}
public void postOrder(TreeNode root){//后序遍历
    if (root==null)
        return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val+" ");

}
//将返回值存储到list
    //1
    public List<TreeNode> prevOrder1(TreeNode root){//前序遍历，递归
       List<TreeNode> list=new ArrayList<>();
        if (root==null)
            return list;
        list.add(root);
        prevOrder1(root.left);
        prevOrder1(root.right);
        return list;
    }
    //2
    public List<TreeNode> prevOrder2(TreeNode root){//前序遍历，递归
        List<TreeNode> list=new ArrayList<>();
        List<TreeNode> leftTree=new ArrayList<>();
        List<TreeNode>rightTree=new ArrayList<>();
        if (root==null)
            return list;
        list.add(root);
        leftTree.addAll(prevOrder2(root.left));
        list.addAll(leftTree);
        rightTree.addAll(prevOrder2(root.right));
        list.addAll(rightTree);
        return list;
    }
    public List<TreeNode> inOrder1(TreeNode root){//中序遍历
        List<TreeNode> list=new ArrayList<>();
        List<TreeNode> leftTree=new ArrayList<>();
        List<TreeNode>rightTree=new ArrayList<>();
        if (root==null)
            return list;
        leftTree.addAll(inOrder1(root.left));
        list.addAll(leftTree);
        list.add(root);
        rightTree.addAll(inOrder1(root.right));
        list.addAll(rightTree);
        return list;
    }
    public List<TreeNode> postOrder1(TreeNode root){//后序遍历
        List<TreeNode> list=new ArrayList<>();
        List<TreeNode> leftTree=new ArrayList<>();
        List<TreeNode> rightTree=new ArrayList<>();
        if (root==null)
            return list;
        leftTree.addAll(postOrder1(root.left));
        list.addAll(leftTree);
        rightTree.addAll(postOrder1(root.right));
        list.addAll(rightTree);
        list.add(root);
        return list;
    }
    //统计节点个数
    //1定义一个size;
    public int size;
    public void NodeSize(TreeNode root){
        if (root==null)
            return;
        NodeSize(root.left);
        NodeSize(root.right);
        size++;
    }
//2
    public int NodeSize2(TreeNode root){
        if (root==null)
            return 0;
        return NodeSize2(root.left)+NodeSize2(root.right)+1;
    }
    //得到叶子节点个数
    //1
    public int leafSize;
    public void getLeafSize(TreeNode root){
        if (root==null)
            return;
        if (root.left==null&&root.right==null)
            leafSize++;
        getLeafSize(root.left);
        getLeafSize(root.right);

    }
    //2使用子问题
    public int getLeafSize2(TreeNode root){
        if (root==null)
            return 0;
        if (root.left==null&&root.right==null)
            return 1;
           return getLeafSize2(root.left)+getLeafSize2(root.right);
    }
    //第k层节点个数
    public int getKnodeCount(TreeNode root,int k){
        if (root==null)
            return 0;
        if (k==1)
            return 1;
        return getKnodeCount(root.left,k-1)+getKnodeCount(root.right,k-1);
    }
//二叉树高度,左子树和右子树高度最大值加1
    public int getHeight(TreeNode root){
        if (root==null)
            return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }
//查找某个值是否在二叉树中
    public boolean find(TreeNode root,char val){
        if (root==null)
            return false;
        if (root.val==val)
            return true;
        boolean leftVal=find(root.left,val);
        if (leftVal==true)
            return true;
        boolean rightVal=find(root.right,val);
        if (rightVal==true)
            return true;
        return false;

    }
    //层序遍历
    public void leverOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null)
            return;
        queue.offer(root);
     while (!queue.isEmpty()){
    TreeNode cur=queue.poll();
    System.out.println(cur.val+" ");
    if (cur.left!=null){
        queue.offer(cur.left);
    }
    if (cur.right!=null){
        queue.offer(cur.right);
    }
}
    }
    //变种
    public List<List<TreeNode>> leverOrder2(TreeNode root){
        List<List<TreeNode>>ret=new ArrayList<>();
            Queue<TreeNode> queue=new LinkedList<>();
        if (root==null)
            return ret;
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<TreeNode> tmp=new ArrayList<>();
            while (size!=0) {
                TreeNode cur = queue.poll();
                tmp.add(cur);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
    //判断是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root==null){
            return true;
        }
                Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if (cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
           TreeNode cur= queue.poll();
           if (cur!=null)
               return false;
        }
        return true;
    }

}
